package DP;

/**
 * @author 曹见朋
 * @create 2024-06-12-20:47
 */
public class Main01Bag2 {

    public static int bag(int[] weights, int[] values, int bag) {
        int m = weights.length;
        int[] dp = new int[bag + 1];

        dp[0] = 0;
        for (int i = 0; i < m; i++) {
            for (int j = bag; j >= weights[i]; j--) {
                    dp[j] = Math.max(dp[j], dp[j - weights[i]] + values[i]);
                }
        }


        for (int j = 0; j <= bag; j++) {
            System.out.print(" " + dp[j]);
        }
        return dp[bag];
    }

    public static void main(String[] args) {
        int[] weight = new int[]{1, 3, 4};
        int[] values = new int[]{15, 20, 30};
        int bag = 4;

        int result = bag(weight, values, bag);
        System.out.println();
        System.out.println(result);
    }
}
